/*
date:20210402 22:29 pm
key:时间复杂度O(对所有非空格子遍历了一次),空间复杂度O(1),通过全部测试点还是超时无语了。通过不停抬高平面来计算底层。
*/
class Solution {
public:
//左右探查第一个大于0的，探查撞车就直接这层没有，从这个探查范围里开始，
int count_lay(vector<int>&lay, int &top, int &i, int &j)
{
    int count=0;
    while(lay[i]<top)
    {
        i++;
    }
    while(lay[j]<top)
    {
        j--;
    }
    
    if(i==j)//这层只有有一个顶峰，如实例第三层
    {
        return -1;
    }
    else
    {
        for(int r=i+1;r<j;r++)
        {
            if(lay[r]<top)
            {
                count++;
            }
        }
    }
    return count;
}

    int trap(vector<int>& height) 
    {
        if(height.size()<2)
        {
            return 0;
        }
        //先遍历一次，得到最高点
        int max_high=0;
        for(auto i:height)
        {
            if(i>max_high)
            {
                max_high=i;
            }
        }

        int count=0;
        int top=1;
        int this_lay;
        int i=0;
        int j=height.size()-1;
        while(max_high--)
        {
            this_lay=count_lay(height,top, i, j);
            //从下往上扫描，如果这层只有一个top，就可以直接跳出了
            if(this_lay==-1)
            {
                break;
                
            }
            else
            {
                count+=this_lay;
            }
            
            ++top;
            
        }

        return count;
    }
};

//将每一层转换成bool数组
// bool *one_lay(vector<int>& height) 
// {
//     bool*lay=new bool[height.size()];
//     //根据这一层初始化
//     for(int i=0;i<height.size();i++)
//     {
//         if(height[i]>0)
//         {
//             lay[i]=1;
//         }
//         else
//         {
//             lay[i]=0;
//         }
//     }
//     return lay;
// }
//输出bool数组
// void print_lay(bool *lay,int size)
// {
//     for(int i=0;i<size;i++)
//     {
//     cout<<lay[i]<<" ";
//     }
// }
//每观察完一层就对整个vector-1；
// void delet1(vector<int>& height)
// {

//     for(int i=0;i<height.size();i++)
//     {
//         --height[i];
//     }
    
// }
大神版 ，总体积减去柱子体积
/*
/*
date:20210402 22:29 pm
key:时间复杂度O(对所有非空格子遍历了一次),空间复杂度O(1),通过全部测试点还是超时无语了。通过不停抬高平面来计算底层。
*/
class Solution {
public:

    int trap(vector<int>& height) 
    {
        if(height.size()<2)
        {
            return 0;
        }
        //先遍历一次，得到最高点
        //先遍历一次，得到最高点
        int max_high=0;
        int max=0;
        for(auto i:height)
        {
            max+=i;
            if(i>max_high)
            {
                max_high=i;
            }
        }
        


        int count=0;
        int top=1;
        int this_lay;
        int i=0;
        int j=height.size()-1;
        while(max_high--)
        {
            this_lay =0;
            while(height[i]<top)
            {
                i++;
            }
            while(height[j]<top)
            {
                j--;
            }
            if(i==j)//这层只有有一个顶峰，如实例第三层
            {
                count++;
                
            }
            else
            {
                this_lay=j-i+1;
            }
            count+=this_lay;
            ++top;
            
        }

    return count-max;
    }
};

//将每一层转换成bool数组
// bool *one_lay(vector<int>& height) 
// {
//     bool*lay=new bool[height.size()];
//     //根据这一层初始化
//     for(int i=0;i<height.size();i++)
//     {
//         if(height[i]>0)
//         {
//             lay[i]=1;
//         }
//         else
//         {
//             lay[i]=0;
//         }
//     }
//     return lay;
// }
//输出bool数组
// void print_lay(bool *lay,int size)
// {
//     for(int i=0;i<size;i++)
//     {
//     cout<<lay[i]<<" ";
//     }
// }
//每观察完一层就对整个vector-1；
// void delet1(vector<int>& height)
// {

//     for(int i=0;i<height.size();i++)
//     {
//         --height[i];
//     }
    
// }
*/